/*
2022-3-13
https://leetcode-cn.com/problems/minimum-weighted-subgraph-with-the-required-paths/
*/ 
class Solution {
public:
    void dij(int s,vector<pair<int,int>>nes[],vector<long long> &dist)
    {
        priority_queue<pair<long long,int>>q;
        dist[s]=0;
        q.push({0,s});
        while(q.size())
        {
            auto [cost,node]=q.top();
            q.pop();
            if(cost>dist[node]) continue;
            for(auto [a,b]:nes[node])
            {
                if(cost+b<dist[a])
                {
                    dist[a]=cost+b;
                    q.push({cost+b,a});
                }
            }
        }
    }

    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        vector<pair<int,int>>f[n],b[n];
        for(auto &e:edges)
        {
            f[e[0]].push_back({e[1],e[2]});
            b[e[1]].push_back({e[0],e[2]});
        }
        vector<long long> dist1(n,1e15),dist2(n,1e15),dist3(n,1e15);
        dij(src1,f,dist1);
        dij(src2,f,dist2);
        dij(dest,b,dist3);
        long long res=1e15;
        for(int i=0;i<n;i++)
        {
            res=min(res,dist1[i]+dist2[i]+dist3[i]);
        }
        if(res>1e12) res=-1;
        return res;

    }
};
